package array;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums 和一个 非负 整数 k 。一次操作中，你可以选择任一元素 加 1 或者减 1 。
 * 请你返回将 nums 中位数 变为 k 所需要的 最少 操作次数。
 * 一个数组的中位数指的是数组按非递减顺序排序后最中间的元素。如果数组长度为偶数，我们选择中间两个数的较大值为中位数。
 * <p>
 * 示例 1：
 * 输入：nums = [2,5,6,8,5], k = 4
 * 输出：2
 * 解释：我们将 nums[1] 和 nums[4] 减 1 得到 [2, 4, 6, 8, 4] 。现在数组的中位数等于 k 。
 * <p>
 * 示例 2：
 * 输入：nums = [2,5,6,8,5], k = 7
 * 输出：3
 * 解释：我们将 nums[1] 增加 1 两次，并且将 nums[2] 增加 1 一次，得到 [2, 7, 7, 8, 5] 。
 * <p>
 * 示例 3：
 * 输入：nums = [1,2,3,4,5,6], k = 4
 * 输出：0
 * 解释：数组中位数已经等于 k 了。
 *
 * @author jishenghuang
 * @version 20250419
 */
public class MinOpsToMakeMedianK_3107 {
    /**
     * 把 nums 从小到大排序后，中位数为 nums[m]，其中 m=⌊n/2⌋，n 为 nums 的长度。
     * 我们需要把中位数左边的数都变成 ≤k 的，右边的数都变成 ≥k 的。
     * <p>
     * 分类讨论：
     * 如果 nums[m]>k，要把下标在 [0,m] 中的大于 k 的数都变成 k，由于下标在 [m+1,n−1] 中的数已经大于 k（因为数组是有序的），所以下标在 [m+1,n−1] 中的数无需操作。
     * 如果 nums[m]<k，要把下标在 [m,n−1] 中的小于 k 的数都变成 k，由于下标在 [0,m−1] 中的数已经小于 k（因为数组是有序的），所以下标在 [0,m−1] 中的数无需操作。
     *
     * @param nums the given array
     * @param k    the target median of the array
     * @return the minimum operations to make the median of the array k
     */
    public static long minOperationsToMakeMedianK(int[] nums, int k) {
        Arrays.sort(nums);
        long ans = 0;
        int m = nums.length / 2;

        if (nums[m] > k) {
            for (int i = m; i >= 0 && nums[i] > k; --i) {
                ans += nums[i] - k;
            }
        } else {
            for (int i = m; i < nums.length && nums[i] < k; ++i) {
                ans += k - nums[i];
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {2, 5, 6, 8, 5};
        int k = 4;
        System.out.println(minOperationsToMakeMedianK(nums, k));

        nums = new int[]{2, 5, 6, 8, 5};
        k = 7;
        System.out.println(minOperationsToMakeMedianK(nums, k));

        nums = new int[]{1, 2, 3, 4, 5, 6};
        k = 4;
        System.out.println(minOperationsToMakeMedianK(nums, k));
    }
}